/*
 * QuickSort.cpp
 *
 *  Created on: 02-09-2013
 *      Author: Krzychu
 */

#include "MaximalShiftQuickSort.h"

#include<iostream>
using namespace std;

MaximalShiftQuickSort::MaximalShiftQuickSort()
{

}

MaximalShiftQuickSort::~MaximalShiftQuickSort()
{

}

int* minShifter;

int maxShiftPcmp(patStruct pat1, patStruct pat2)
{
	int dsh;

	dsh = minShifter[pat2.loc] - minShifter[pat1.loc];
	return (dsh ? dsh : (pat2.loc - pat1.loc));
}

int MaximalShiftQuickSort::partition(patStruct* data, int l, int r)
{
	int result;

	patStruct x = data[l];
	patStruct w;
	int i = l, j = r;
	while (true)
	{
		while (maxShiftPcmp(data[j], x) > 0)
		{
			j--;
		}
		while (maxShiftPcmp(data[i], x) > 0)
		{
			i++;
		}
		if (i < j)
		{
			w = data[i];
			data[i] = data[j];
			data[j] = w;
			i++;
			j--;
		}
		else
		{
			result = j;
			break;
		}
	}

	return result;
}

void MaximalShiftQuickSort::sort(patStruct* data, int l, int r)
{
	int q;
	if (l < r)
	{
		q = partition(data, l, r);
		sort(data, l, q);
		sort(data, q + 1, r);
	}
}

void MaximalShiftQuickSort::sort(patStruct* data, int r, int* minShift)
{
	minShifter = minShift;

	sort(data, 0, r - 1);
}
